Random number generators have many uses in conjunction with computer applications. They are used in simulation. They are used in communications. For example, such numbers can be used in Ethernet adapters for retransmission when collisions occur. Random numbers can also be used for encryption and decryption of data.
Many of the random number generators available use some electrical phenomenon to generate their random numbers. They can be fast, and the random numbers generated can be quite random. These random number generators cannot generate reproducible sequences of random numbers. Thus, they are useless for simulation, encryption, and decryption.
There are available several random number generators that do generate reproducible sequences of random numbers. The sequence of numbers generated invariably do not perform well according to standard tests applied to determine randomness. The ones that do produce somewhat more random sequences are usually slow.
The present invention produces a reproducible sequence of highly random numbers efficiently. These numbers test as being significantly more random than those of the other methods tested that produced reproducible random number sequences.
The current invention produces its stream of highly random numbers in two phases. First, an intermediate random number is generated by a standard method. Then, the intermediate random number is combined with a history of previous intermediate random numbers to generate a final or output random number. The second step or phase increases the randomness of the numbers produced significantly.
The following is the prior art known to the inventor that might be pertinent to the patent examiner in the examination of this patent.
U.S. Pat. No. 3,548,174 by Donald Knuth describes a generator that produces a reproducible sequence of random numbers. The Knuth invention is a one phase generator. By using a two phase process or apparatus, the instant invention is capable of generating numbers that are significantly more random.
U.S. Pat. No. 3,811,038 by Stewart Reddaway describes a random number generator where the numbers generated follow a Gaussian distribution instead of a uniform distribution. This Gaussian distribution generator by its very nature generates some numbers significantly more frequently than others. The numbers generated by the instant invention follow a uniform distribution.
U.S. Pat. No. 4,047,008 by Frank Perkins describes a random number generator that depends on random access memory to replace shift registers. It generates long pseudo random bit sequences slowly. It has sacrificed statistical randomness for the ability to generate long bit sequences.
U.S. Pat. No. 4,355,366 by Sigmund Porter describes an apparatus for generating random numbers based on the use of white noise. The series of random numbers produced is not reproducible, and is therefore unusable in many applications.
U.S. Pat. No. 4,408,298 by Kim Ruhland describes a special purpose random number generator that produces a succession of numbers manifesting solely three values at random from two-bits Statistical randomness has been sacrificed for speed.
U.S. Pat. No. 4,791,594 by Kevin Harney et al. describes a random number generator where the numbers returned correspond to input indices, such that given a specific seed, whenever a specific index is used, the same random number is returned. Its primary use is with video games. It is custom tailored for video game applications, and has sacrificed statistical randomness for the ability to randomly access the numbers in a random number sequence.
U.S. Pat. No. 4,890,252 by Charles Wang describes a random number generator that sacrifices statistical randomness for an increased period.
U.S. Pat. No. 4,901,264 by Mishio Hayashi describes a random number generator that extracts partial numbers from random access memory of a computer, building each random number generated from a plurality of such partial random numbers. The instant invention does not require an array or table of numbers as does the Hayashi invention.
Algorithms by Robert Sedgewick, Addison-Wesley Publishing, ISBN 0-201-006672-6, has a chapter on random numbers. A two phase random number generation algorithm is described in which random numbers are stored in a table in the first phase, and extracted in a pseudo-random order from the table in the second phase. No such table is required in the present invention.
The Art of Computer Programming, Second Edition, Volume 2, Seminumerical Algorithms, by Donald E. Knuth, Addison-Wesley Publishing, ISBN 0-201-03822-6, contains the same random number generation algorithm as found in the Knuth patent listed above. Several extremely similar algorithms are also shown. No two phase random number generators are shown.